package linear;

import java.util.Iterator;

public class Queue<T> implements Iterable<T> {
    //记录首结点
    private Node head;
    //记录队列元素个数
    private int N;
    //记录尾结点
    private Node last;

    public Queue() {
        head = new Node(null, null);
        last = null;
        N = 0;
    }

    //判断队列是否为空
    boolean isEmpty() {
        return N == 0;//head.next==null
    }

    //获取队列中的元素个数
    public int size() {
        return N;
    }

    //向队列尾部插入元素
    public void enqueue(T t) {
        if (isEmpty()) {
            //链表为空
            //创建一个新的结点
            Node newNode = new Node(t, null);
            //头结点的下一个结点指向我们新创建的结点
            head.next = newNode;
            //尾结点指向新创建的结点，保证last指针始终指向链表的最后一个结点
            last = newNode;
        } else {
            //链表不为空
            //创建一个新的结点
            Node newNode = new Node(t, null);
            //尾结点指向新的结点，保证last指针始终指向链表的最后一个结点
            last.next = newNode;
            last=newNode;
        }
        N++;
    }

    //从队列中删除一个元素，返回元素数据
    public T dequeue() {
        if (isEmpty()) {
            return null;
        }
        Node n = head.next;
        head.next = n.next;
        N--;
        if (isEmpty()) {
            last = null;
        }
        return (T) n.item;
    }

    @Override
    public Iterator iterator() {
        return new QIterator();
    }

    private class QIterator implements Iterator<T> {
        private Node node = head;

        @Override
        public boolean hasNext() {
            return node.next != null;
        }

        @Override
        public T next() {
            node = node.next;
            return (T) node.item;
        }
    }
}
